// @algorithm @lc id=30 lang=cpp 
// @title substring-with-concatenation-of-all-words


// #define print(...)
// @test("barfoothefoobarman",["foo","bar"])=[0,9]
// @test("wordgoodgoodgoodbestword",["word","good","best","word"])=[]
// @test("barfoofoobarthefoobarman",["bar","foo","the"])=[6,9,12]
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
    vector<int> res;
    auto width = words[0].size();
    auto num = words.size();
    unordered_map<string, int> cntWords;
    for(auto &w : words)
        cntWords[w]++;
    for(size_t offset=0; offset<width; offset++){
        auto left = offset, right = left; // 滑动窗口
        unordered_map<string,int> cntInWin; // 窗口中有效 word 数量 
        while(right < s.size()-width+1){
            auto word = s.substr(right, width);
            right += width;
            if(0>=cntWords.count(word)){ // word 无效
                left = right;
                cntInWin.clear();
                continue;
            }
            cntInWin[word]++;
            while(cntWords[word] < cntInWin[word]){ // word 重复次数过多
                cntInWin[s.substr(left, width)]--;
                left += width;
            }
            if(left + width*num == right){
                res.push_back(left);
                cntInWin[s.substr(left, width)]--;
                left += width;
            }
        }
    }
    return res;
}
};